package 纯数组;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-13
 **/

public class No378有序矩阵中第K小的元素 {

    /**
     * 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
     * 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
     *
     * 示例 1：
     * 输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
     * 输出：13
     * 解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
     * 示例 2：
     * 输入：matrix = [[-5]], k = 1
     * 输出：-5
     *
     * 提示：
     * n == matrix.length
     * n == matrix[i].length
     * 1 <= n <= 300
     * -109 <= matrix[i][j] <= 109
     * 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
     * 1 <= k <= n2
     */

    /**
     * 总共三种解法
     * 1. 朴素全遍历排序解法
     * 2. k个链表排序解法(用到一条有序性质)
     * 3. 二分查找 mid排位 法(用到两条有序性质)
     */

    // 朴素解法
    public int kthSmallestNo1(int[][] matrix, int k) {

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k,(i1, i2)->i2-i1);

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                int num = matrix[i][j];
                if (priorityQueue.size() < k) {
                    priorityQueue.add(num);
                    continue;
                }
                if (priorityQueue.peek() < num) {
                    continue;
                }
                priorityQueue.poll();
                priorityQueue.add(num);
            }
        }

        return priorityQueue.peek();
    }

    // k条有序数组解法
    public int kthSmallestNo2(int[][] matrix, int k) {

        int allLength = matrix.length;
        int itemLength = matrix[0].length;

        // 3{当前数组序号,当前下标} 头小的排前面
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(matrix.length, (o1, o2) -> {
            return matrix[o1[0]][o1[1]] - matrix[o2[0]][o2[1]];
        });

        for (int i = 0; i < matrix.length; i++) {
            priorityQueue.add(new int[]{i,0});
        }

        // 开始排序
        while (k != 1) {

            int[] poll = priorityQueue.poll();
            k--;
            if (poll[1] + 1 == itemLength) {
                continue;
            }
            poll[1] += 1;
            priorityQueue.add(poll);

        }

        int[] peek = priorityQueue.peek();
        return matrix[peek[0]][peek[1]];
    }

    // 二分解法
    public int kthSmallestNo3(int[][] matrix, int k) {

        int allLength = matrix.length;
        int itemLength = matrix[0].length;
        int left = matrix[0][0];
        int right = matrix[allLength - 1][itemLength - 1];

        while (left < right) {
            int midNum = (right - left) / 2 + left;
            int count = minNumCount(matrix, midNum);
            if (count < k) {
                left = midNum + 1;
            } else {
                right = midNum;
            }
        }

        return left;
    }

    private int minNumCount(int[][] arr, int num) {
        int count = 0;
        // 找出每一排比num小的元素个数
        int i = arr.length - 1;
        int j = 0;
        while (i >= 0 && j < arr[0].length) {

            if (arr[i][j] <= num) {
                count += (i + 1);
                j++;
            } else {
                i--;
            }

        }

        return count;
    }

    public static void main(String[] args) {
        int[][] arr = {{1,5,9},{10,13,13},{13,13,15}};
        No378有序矩阵中第K小的元素 n = new No378有序矩阵中第K小的元素();
        int result = n.kthSmallestNo1(arr, 8);
        System.out.println(result);
        result = n.kthSmallestNo2(arr, 8);
        System.out.println(result);
        result = n.kthSmallestNo3(arr, 8);
        System.out.println(result);
    }

}
